package agorithm.week1.classOne;


import agorithm.bean.ListNode;

/**
 *
 * 142. 环形链表 II
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 *
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
 *
 * 说明：不允许修改给定的链表。
 *
 * 进阶：
 *
 * 你是否可以使用 O(1) 空间解决此题？
 *
 * @author zcc
 * @date 2021/06/18/18:41
 */
public class DetectCycle {
    public static void main(String[] args) {
        String s = "(){}}{";
        ListNode listNode = ListNode.getNode();
        System.out.println("detectCycle = " + detectCycle(listNode));
    }

    public static ListNode detectCycle(ListNode head) {
        return hasCycle(head);
    }
    public static ListNode hasCycle(ListNode head) {
        ListNode solw = head;
        ListNode fast = head;
        boolean pos = false;
        while (solw != null && fast != null && fast.next != null) {
            solw = solw.next;
            fast = fast.next.next;
            if (solw == fast) {
                pos = true;
                break;
            }
        }
        if (pos) {
            while (solw != null && head != null) {
                if (solw == head) {
                    return solw;
                }
                solw = solw.next;
                head = head.next;
            }
        }
        return null;
    }
}
